package com.fw.algorithm.sort;

import java.util.Arrays;

/**
 * 希尔排序
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] arr = {0,2,10,1,8,7,3,9,6};
        shellSoftFinal(arr);

    }

    /**
     * 希尔排序深度解刨 —— 移位法最终版 - 推荐 满星，大数据排序首选
     */
    public static void shellSoftFinal(int ...arr){
        for (int gap = arr.length / 2 ; gap >0 ; gap /= 2) {
            // 采用直接插入的思维，进行元素选到指定位置进行插入
            for (int i = gap;i < arr.length;i ++){
                int j = i;
                int temp = arr[j];
                if (arr[j - gap] > temp){
                    // 选择位置
                    while (j - gap >= 0  && temp < arr[j - gap]){
                        // 移动
                        arr[j] =  arr[j - gap];
                        j -= gap;

                    }
                    // 找到位置
                    arr[j] =temp;
                }
            }

            }
        System.out.printf("希尔排序%s\n", Arrays.toString(arr));

    }

    /**
     * 希尔排序深度解刨 —— 交换法最终版- 效率过低，不大推荐
     */
    public static void shellSoftFinalNo(int ...arr){
        int temp = 0;
        for (int gap = arr.length / 2 ; gap >0 ; gap /= 2){
            for (int i = gap; i < arr.length; i++) {
                for (int j = i - gap;j >= 0 ; j-=gap){
                    if (arr[j] > arr[j + gap]){
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }

                }

            }
        }
        System.out.printf("希尔排序%s\n", Arrays.toString(arr));


    }


    /**
     * 希尔排序深度解刨 —— 交换法
     * @param arr
     */
    public static void shellSort(int ...arr){

        /**
         * 1。 希尔排序思路就是 数组 整除 每次得到对半数据，进行比对，对等分组。
         * 2。 最终排为一组，从而进行排序
         */
        // 假设该数组是 10 个元素，取模 2 = 5
        int temp = 0;
        for (int i = 5; i < arr.length; i++) {
            for (int j = i - 5;j >= 0 ; j-=5){
                if (arr[j] > arr[j + 5]){
                     temp = arr[j];
                     arr[j] = arr[j + 5];
                     arr[j + 5] = temp;
                }

            }
            
        }
        System.out.printf("第一次希尔排序%s\n", Arrays.toString(arr));


        for (int i = 2; i < arr.length; i++) {
            for (int j = i - 2;j >= 0 ; j-=2){
                if (arr[j] > arr[j + 2]){
                    temp = arr[j];
                    arr[j] = arr[j + 2];
                    arr[j + 2] = temp;
                }

            }

        }
        System.out.printf("第二次希尔排序%s\n", Arrays.toString(arr));


        for (int i = 1; i < arr.length; i++) {
            for (int j = i - 1;j >= 0 ; j-=1){
                if (arr[j] > arr[j + 1]){
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }

            }

        }
        System.out.printf("第三次希尔排序%s\n", Arrays.toString(arr));

    }
}
